package com.lun.swordtowardoffer2.c06;

import java.util.LinkedList;
import java.util.Stack;

public class AsteroidCollision {

	public int[] asteroidCollision(int[] asteroids) {
		LinkedList<Integer> stack = new LinkedList<>();
		//用LinkedList的话，不能通过单元测试，需逆序操作后才能通过
//		Stack<Integer> stack = new Stack<>();
		
		for(int asteroid : asteroids) {
			
			while(!stack.isEmpty() && stack.peek() > 0 && asteroid < 0) {//碰撞
				int diff = stack.peek() + asteroid;
				
				if(diff == 0) {//互灭
					stack.pop();
					break;
				}else if(diff < 0) {//继续撞
					stack.pop();
				}else {//自毁
					break;
				}
			}
			
			if(stack.isEmpty() || !(stack.peek() > 0 && asteroid < 0)) {
				stack.push(asteroid);
			}
		}
		
		return stack.stream().mapToInt(i->i).toArray();
	}
	
}
